#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <thread>
#include <mutex>
#include <chrono>
#include <set>
#include <cmath>
#include <map>
using namespace std;

// 方法一的函数和变量
vector<vector<size_t>> best_combination1;
size_t min_total_length1 = SIZE_MAX;

// 方法二的函数和变量
size_t sum2 = 0;


// 存储路径信息的结构体
struct Path {
    vector<size_t> nodes;  // 路径上的节点序列
    size_t length;         // 路径总长度

    // 重载运算符，用于优先队列按路径长度升序排列
    bool operator>(const Path& other) const {
        return length > other.length;
    }
};

// 方法一的函数
bool dfs1(size_t start, size_t end, const vector<vector<size_t>>& roadlength1, vector<bool>& visited1, vector<size_t>& current_path1, vector<vector<size_t>>& all_paths1, size_t k1) {
    visited1[start] = true;
    current_path1.push_back(start);

    if (start == end) {
        all_paths1.push_back(current_path1);
        if (all_paths1.size() > k1) {
            current_path1.pop_back();
            visited1[start] = false;
            return false;
        }
    } else {
        for (size_t i = 0; i < roadlength1.size(); i++) {
            if (roadlength1[start][i] != INT_MAX && !visited1[i]) {
                if (!dfs1(i, end, roadlength1, visited1, current_path1, all_paths1, k1)) {
                    current_path1.pop_back();
                    visited1[start] = false;
                    return false;
                }
            }
        }
    }

    current_path1.pop_back();
    visited1[start] = false;
    return true;
}

vector<size_t> dijkstra1(size_t start, size_t end, const vector<vector<size_t>>& roadlength1) {
    const size_t INF = INT_MAX;
    const size_t n = roadlength1.size();
    vector<size_t> dist1(n, INF);
    dist1[start] = 0;
    vector<size_t> prev1(n, INF);

    priority_queue<pair<size_t, size_t>, vector<pair<size_t, size_t>>, greater<pair<size_t, size_t>>> pq1;
    pq1.push({0, start});

    while (!pq1.empty()) {
        auto [d, u] = pq1.top();
        pq1.pop();

        if (u == end) break;
        if (d > dist1[u]) continue;

        for (size_t v = 0; v < n; ++v) {
            if (roadlength1[u][v] != INF && dist1[v] > dist1[u] + roadlength1[u][v]) {
                dist1[v] = dist1[u] + roadlength1[u][v];
                prev1[v] = u;
                pq1.push({dist1[v], v});
            }
        }
    }

    if (dist1[end] == INF) return {};

    vector<size_t> path1;
    for (size_t cur = end; cur != start; cur = prev1[cur]) {
        if (prev1[cur] == INF) return {};
        path1.push_back(cur);
    }
    path1.push_back(start);

    reverse(path1.begin(), path1.end());
    return path1;
}
// 计算路径的总长度
size_t calculatePathLength(const vector<size_t>& path, const vector<vector<size_t>>& roadlength) {
    size_t length = 0;
    for (size_t i = 0; i < path.size() - 1; ++i) {
        length += roadlength[path[i]][path[i + 1]];  // 累加路径中每条边的长度
    }
    return length;
}

vector<vector<size_t>> yen_ksp1(size_t start, size_t end, size_t k1, const vector<vector<size_t>>& roadlength1) {
    vector<vector<size_t>> P1;
    if (k1 == 0) return P1;

    auto firstPath1 = dijkstra1(start, end, roadlength1);
    if (firstPath1.empty()) return P1;
    P1.push_back(firstPath1);

    priority_queue<Path, vector<Path>, greater<Path>> Q1;
    set<vector<size_t>> usedPaths1;
    usedPaths1.insert(firstPath1);

    for (size_t i = 0; i < firstPath1.size() - 1; ++i) {
        size_t r = firstPath1[i];
        size_t s = firstPath1[i + 1];

        vector<vector<size_t>> modified_roadlength1 = roadlength1;
        modified_roadlength1[r][s] = INT_MAX;
        modified_roadlength1[s][r] = INT_MAX;

        auto spurPath1 = dijkstra1(r, end, modified_roadlength1);
        if (!spurPath1.empty()) {
            vector<size_t> newPath1(firstPath1.begin(), firstPath1.begin() + i + 1);
            newPath1.insert(newPath1.end(), spurPath1.begin() + 1, spurPath1.end());

            set<size_t> nodesInPath1(newPath1.begin() + 1, newPath1.end() - 1);
            if (nodesInPath1.size() == newPath1.size() - 2) {
                size_t newLen1 = calculatePathLength(newPath1, roadlength1);

                if (!usedPaths1.count(newPath1)) {
                    usedPaths1.insert(newPath1);
                    Q1.push({newPath1, newLen1});
                }
            }
        }
    }

    while (!Q1.empty() && P1.size() < k1) {
        Path candidate1 = Q1.top();
        Q1.pop();

        bool duplicate = false;
        for (auto &p : P1) {
            if (p == candidate1.nodes) {
                duplicate = true;
                break;
            }
        }
        if (duplicate) continue;

        P1.push_back(candidate1.nodes);

        for (size_t i = 0; i < candidate1.nodes.size() - 1; ++i) {
            size_t r = candidate1.nodes[i];
            size_t s = candidate1.nodes[i + 1];

            vector<vector<size_t>> modified_roadlength1 = roadlength1;
            modified_roadlength1[r][s] = INT_MAX;
            modified_roadlength1[s][r] = INT_MAX;

            auto spurPath1 = dijkstra1(r, end, modified_roadlength1);
            if (!spurPath1.empty()) {
                vector<size_t> newPath1(candidate1.nodes.begin(), candidate1.nodes.begin() + i + 1);
                newPath1.insert(newPath1.end(), spurPath1.begin() + 1, spurPath1.end());

                set<size_t> nodesInPath1(newPath1.begin() + 1, newPath1.end() - 1);
                if (nodesInPath1.size() == newPath1.size() - 2) {
                    size_t newLen1 = calculatePathLength(newPath1, roadlength1);

                    if (!usedPaths1.count(newPath1)) {
                        usedPaths1.insert(newPath1);
                        Q1.push({newPath1, newLen1});
                    }
                }
            }
        }
    }

    return P1;
}
// 检测当前车辆路径组合是否会导致堵车
struct Event1 {
    size_t time;
    size_t u; // 起始节点
    size_t v; // 结束节点
    bool enter; // 进入路段（true）还是离开路段（false）
    // 重载比较运算符，使优先队列按时间升序排列
    bool operator>(const Event1& other) const {
        return time > other.time;
    }
};
// 堵车检测
bool checkTraffic(const vector<vector<size_t>>& combination,
                  const vector<vector<size_t>>& roadlength,
                  const vector<vector<size_t>>& restrictions) {
    
    map<size_t, vector<Event1>> eventMap;

    // 将每辆车的行驶过程转化为事件
    for (const auto& path : combination) {
        size_t current_time = 0;
        for (size_t i = 1; i < path.size(); ++i) {
            size_t u = path[i - 1];
            size_t v = path[i];
            size_t length = roadlength[u][v];

            // 车辆进入(u->v)的事件
            eventMap[current_time].push_back({current_time, u, v, true});
            // 车辆离开(u->v)的事件
            eventMap[current_time + length].push_back({current_time + length, u, v, false});

            current_time += length;
        }
    }

    // 记录当前每条道路的流量
    vector<vector<size_t>> current_flow(roadlength.size(), vector<size_t>(roadlength.size(), 0));

    // 处理事件
    for (const auto& [current_time, events] : eventMap) {
        vector<Event1> sameTimeEvents = events;

        // 先处理离开事件，释放流量
        for (auto& event : sameTimeEvents) {
            if (!event.enter) {
                if (current_flow[event.u][event.v] > 0) {
                    current_flow[event.u][event.v]--;
                    current_flow[event.v][event.u]--;
                }
            }
        }

        // 再处理进入事件，增加流量
        for (auto& event : sameTimeEvents) {
            if (event.enter) {
                current_flow[event.u][event.v]++;
                current_flow[event.v][event.u]++;
                if (current_flow[event.u][event.v] > restrictions[event.u][event.v]) {
                    return false;  // 流量超限，发生堵车
                }
            }
        }
    }

    return true;  // 所有事件处理完毕，未发生堵车
}

// 计算当前组合的总路径长度
size_t calculateTotalLength(const vector<vector<size_t>>& combination, const vector<vector<size_t>>& roadlength) {
    size_t total_length = 0;
    for (const vector<size_t>& path : combination) {
        for (size_t i = 1; i < path.size(); i++) {
            size_t u = path[i - 1];
            size_t v = path[i];
            total_length += roadlength[u][v];
        }
    }
    return total_length;
}


// 回溯遍历所有车辆路径组合,return 1表示超时返回，return 0表示正常返回
size_t traverseCombinations(const vector<vector<vector<size_t>>>& all_cars_paths,
                          size_t car_index,
                          vector<vector<size_t>>& current_combination,
                          const vector<vector<size_t>>& roadlength,
                          const vector<vector<size_t>>& restrictions,
                          vector<vector<size_t>>& best_combination,
                          size_t& min_total_length) {
    static auto start_time = chrono::high_resolution_clock::now();
    // 如果已经处理完所有车辆，检查当前组合是否最优
    if (car_index == all_cars_paths.size()) {
        static size_t num=0;
        num++;
        size_t total_length = calculateTotalLength(current_combination, roadlength);
        if (total_length < min_total_length) {
            
            if (checkTraffic(current_combination, roadlength, restrictions)) {
                min_total_length = total_length;
                best_combination = current_combination;
            }
        }
        // 检测是否运行到第 19.5 秒，每10000个循环检查一次，不然太耗时间
        //static int co=0;
        if (num>10000){
            num=0;
            auto current_time = chrono::high_resolution_clock::now();
            auto elapsed_time = chrono::duration_cast<chrono::milliseconds>(current_time - start_time).count();
            //cout<<++co<<endl;
            if (elapsed_time >= 19500) { // 19.5 秒 = 19500 毫秒
                return 1; // 提前返回
            }
        }
        return 0;
    }

    // 遍历当前车辆的所有候选路径
    for (const auto &path : all_cars_paths[car_index]) {
        current_combination.push_back(path);
        // 递归处理下一辆车
        if(traverseCombinations(all_cars_paths, car_index + 1, current_combination,
                             roadlength, restrictions, best_combination,
                             min_total_length)){
            return 1;
        }
        // 回溯，撤销选择
        current_combination.pop_back();
    }
    return 0;
}

size_t findBestCombination1(const vector<vector<vector<size_t>>>& all_cars_paths1,
                         const vector<vector<size_t>>& roadlength1,
                         const vector<vector<size_t>>& restrictions1) {
    vector<vector<size_t>> current_combination1;
    return traverseCombinations(all_cars_paths1, 0, current_combination1,
                         roadlength1, restrictions1, best_combination1,
                         min_total_length1);
}

// 方法二的函数
struct Event2 {
    size_t time;
    size_t car_id;
    size_t from;
    size_t to;
    Event2(size_t time, size_t id, size_t a, size_t b) : time(time), car_id(id), from(a), to(b) {}

    bool operator<(const Event2& next) const {
        return this->time > next.time;
    }
};

vector<size_t> dijkstra2(size_t N, size_t start, size_t end, const vector<vector<size_t>>& roadlength2, const vector<vector<size_t>>& flow2, const vector<vector<size_t>>& restrictions2) {
    vector<size_t> distance2(N, INT_MAX);
    vector<size_t> previous2(N, -1);
    vector<bool> visited2(N, false);

    distance2[start] = 0;

    for (size_t i = 0; i < N - 1; i++) {
        size_t min_distance = INT_MAX;
        size_t stop = start;

        for (size_t j = 0; j < N; j++) {
            if (!visited2[j] && distance2[j] < min_distance) {
                min_distance = distance2[j];
                stop = j;
            }
        }

        visited2[stop] = true;

        for (size_t k = 0; k < N; k++) {
            if (!visited2[k] && roadlength2[stop][k] < INT_MAX && flow2[stop][k] < restrictions2[stop][k] && distance2[stop] + roadlength2[stop][k] < distance2[k]) {
                distance2[k] = distance2[stop] + roadlength2[stop][k];
                previous2[k] = stop;
            }
        }
    }

    vector<size_t> path2;
    size_t node = end;
    while (node != -1) {
        path2.push_back(node);
        node = previous2[node];
    }
    reverse(path2.begin(), path2.end());

    return path2;
}

void method2(const vector<vector<size_t>>& roadlength2, const vector<vector<size_t>>& restrictions2, const vector<vector<size_t>>& cars2,vector<vector<size_t>>& history2) {
    size_t N = roadlength2.size();
    size_t M = cars2.size();

    vector<vector<size_t>> flow2(N, vector<size_t>(N, 0));
    priority_queue<Event2> event_queue2;
    vector<vector<size_t>> paths2(M);
    
    vector<size_t> car_arrival_time2(M, -1);

    for (size_t i = 0; i < M; i++) {
        paths2[i] = dijkstra2(N, cars2[i][0], cars2[i][1], roadlength2, flow2, restrictions2);

        if (paths2[i].size() == 1) {
            if (paths2[i][0] == cars2[i][0]) {
                car_arrival_time2[i] = 0;
                history2[i].push_back(cars2[i][0]);
                history2[i].push_back(cars2[i][0]);
                continue;
            } else {
                history2[i].push_back(cars2[i][0]);
                event_queue2.push(Event2(1, i, cars2[i][0], cars2[i][0]));
                continue;
            }
        }

        history2[i].push_back(cars2[i][0]);
        size_t u = paths2[i][0];
        size_t v = paths2[i][1];
        size_t time = roadlength2[u][v];
        event_queue2.push(Event2(time, i, u, v));
        flow2[u][v]++;
        flow2[v][u]++;

        paths2[i].erase(paths2[i].begin());
    }

    while (!event_queue2.empty()) {
        size_t current_time = event_queue2.top().time;

        vector<Event2> current_events2;
        while (!event_queue2.empty() && event_queue2.top().time == current_time) {
            Event2 event = event_queue2.top();
            current_events2.push_back(event);
            event_queue2.pop();
            if (event.from != event.to) {
                flow2[event.from][event.to]--;
                flow2[event.to][event.from]--;
                history2[event.car_id].push_back(event.to);
            }
        }
        for (Event2 event : current_events2) {
            if (event.to == cars2[event.car_id][1]) {
                car_arrival_time2[event.car_id] = current_time;
            } else {
                vector<size_t> newpath = dijkstra2(N, history2[event.car_id].back(), cars2[event.car_id][1], roadlength2, flow2, restrictions2);
                if (newpath.size() == 1) {
                    event_queue2.push(Event2(current_time + 1, event.car_id, event.from, event.to));
                    continue;
                } else {
                    paths2[event.car_id] = newpath;
                    size_t u = newpath[0];
                    size_t v = newpath[1];
                    flow2[u][v]++;
                    flow2[v][u]++;
                    size_t travel_time = current_time + roadlength2[u][v];
                    event_queue2.push(Event2(travel_time, event.car_id, u, v));
                }
            }
        }
    }

    sum2 = 0;
    for (size_t i = 0; i < M; i++) {
        sum2 += car_arrival_time2[i];
    }
}

// 主函数
int main() {
    size_t N, M;
    cin >> N >> M;

    vector<vector<size_t>> roadlength1(N, vector<size_t>(N, INT_MAX));
    vector<vector<size_t>> restrictions1(N, vector<size_t>(N, 0));
    vector<vector<size_t>> cars1(M, vector<size_t>(2));

    vector<vector<size_t>> roadlength2(N, vector<size_t>(N, INT_MAX));
    vector<vector<size_t>> restrictions2(N, vector<size_t>(N, 0));
    vector<vector<size_t>> cars2(M, vector<size_t>(2));

    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 0; j < N; ++j) {
            cin >> roadlength1[i][j];
            roadlength2[i][j] = roadlength1[i][j];
            if (roadlength1[i][j] == 0 && i != j) {
                roadlength1[i][j] = INT_MAX;
                roadlength2[i][j] = INT_MAX;
            }
        }
    }

    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 0; j < N; ++j) {
            cin >> restrictions1[i][j];
            restrictions2[i][j] = restrictions1[i][j];
        }
    }

    for (size_t i = 0; i < M; ++i) {
        cin >> cars1[i][0] >> cars1[i][1];
        cars1[i][0]--;
        cars1[i][1]--;
        cars2[i][0] = cars1[i][0];
        cars2[i][1] = cars1[i][1];
    }

    
    // 计算每辆车的候选路径数量 k
    size_t k =(size_t)pow(INT_MAX, 2.0/(M+N))+1;

    // 存储每辆车的候选路径
    vector<vector<vector<size_t>>> all_cars_paths(M);

    // 为每辆车生成前 k 条最短路径
    for (size_t i = 0; i < M; ++i) {
        size_t start = cars1[i][0];
        size_t end = cars1[i][1];

        // 使用 DFS 查找所有路径
        vector<bool> visited(N, false);
        vector<size_t> current_path;
        vector<vector<size_t>> all_paths;
        
        if (dfs1(start, end, roadlength1, visited, current_path, all_paths, k)) {
            // 如果路径数量 <= k，直接使用 DFS 的结果
            all_cars_paths[i] = all_paths;
            //cout<<"Car "<<i+1<<" "<<all_paths.size()<<endl;
            
        } else {
            // 如果路径数量 > k，使用 Yen's Algorithm 找到前 k 条最短路径
            all_cars_paths[i] = yen_ksp1(start, end, k, roadlength2);
            
        }
    }



    // 方法一和方法二的线程
    size_t timeout_flag = 0;
    thread t1([&]() {
        timeout_flag = findBestCombination1(all_cars_paths, roadlength1, restrictions1);
    });

    vector<vector<size_t>> history2(M);
    thread t2([&]() {
        method2(roadlength2, restrictions2, cars2,history2);
    });

    t1.join();
    t2.join();

    // 根据是否超时决定输出
    if (timeout_flag == 0) {
        // 方法一未超时，输出方法一的结果
        //cout << "Method 1 result:" << endl;
        for (size_t i = 0; i < best_combination1.size(); i++) {
            //cout << "Car " << i + 1 << " path: ";
            for (size_t node : best_combination1[i]) {
                cout << node + 1;
                if (node!=cars1[i][1])cout<<" ";
            }
            cout<<endl;
        }
        cout << min_total_length1 << endl;
    } else {
        // 方法一超时，比较方法一和方法二的结果
        //cout << "Method 1 timed out." << endl;
        if (min_total_length1 <= sum2) {
            //cout << "Method 1 is better: " << min_total_length1 << endl;
            for (size_t i = 0; i < best_combination1.size(); i++) {
            
                for (size_t node : best_combination1[i]) {
                    cout << node + 1;
                    if (node!=cars1[i][1])cout<<" ";
                }
                cout<<endl;
            }
            cout << min_total_length1 << endl;
        } else {
            //cout << "Method 2 is better: " << sum2 << endl;
            for (size_t i = 0; i<M;i++){
                for (size_t node:history2[i]){
                    cout<<node+1;
                    if (node!=cars2[i][1])cout<<" ";
                }
                cout<<endl;
            }
            
            cout<<sum2<<endl;
        }
    }
    
    return 0;
}